package com.berchen.算法.排序;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 基数排序
 */
public class BaseSort {
    public static void main(String[] args) {
        int size = 80000;
        int[] testArr = new int[size];
        for (int i = 0; i < size; i++) {
            testArr[i] = (int) (Math.random() * 80000);
        }

        Instant start=Instant.now();
        baseSort(testArr);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); // 156
//        System.out.println(Arrays.toString(testArr));
    }

    public static void baseSort(int arr[]) {

        int[][] tempArr=new int[10][arr.length];
        int [] tempIndex=new int[10];
        int maxLength=maxLength(arr);
        int index=0;
        String tempStr="";
        for(int i =0;i<maxLength;i++){
            for(int j=0;j<arr.length;j++){
                tempStr=arr[j]+"";
                int tempLength=maxLength-tempStr.length();
                for(int k =0;k<tempLength;k++){
                    tempStr="0"+tempStr;
                }
                index=Integer.parseInt(tempStr.toCharArray()[maxLength-i-1]+"");
                tempArr[index][tempIndex[index]]=arr[j];
                tempIndex[index]=tempIndex[index]+1;
            }
            index=0;
            for(int j=0;j<10;j++){
                for(int k=0;k<tempIndex[j];k++) {
                    arr[index++] = tempArr[j][k];
                }
                tempIndex[j]=0;
            }
        }


    }

    public static int maxLength(int[] arr) {
        int maxLength=0;
        for(int i =0;i<arr.length;i++){
            maxLength=maxLength>(arr[i]+"").length()?maxLength:(arr[i]+"").length();
        }
        return maxLength;

    }
}
